1. Field of the Invention
The present invention relates to a method for processing of a single raster element of a skeletonized binary image through the use of tiles.
2. Description of the Related Art
An image skeleton represents the basic structure of an image and is created by decomposing the widths of raster objects in the image to uniform single pixel widths. This simplifies the task of certain recognition systems from character recognition to geometrical recognition.
The current state of the art provides a process for skeletonization of an image by stripping one layer of pixels after another. The process continues until the set of pixels left form a one pixel wide line and is defined as separating two xe2x80x9coffxe2x80x9d areas. This process is known as raster xe2x80x9cthinningxe2x80x9d or xe2x80x9cerosion.xe2x80x9d
The problems associated with the current skeletonization processes include their relatively slow speed and extensive memory utilization requirements. In order to skeletonize the image using the current techniques, two copies of the image must be maintained in memory. For large images, this could mean storing an extraordinary, amount of data. The larger the data file, the greater the access time. Therefore, the process of data retrieval and storage increases in time with the increased amount of data stored.
Also, every pixel in the image is evaluated regardless of whether the pixel will be removed or ignored. This requires a substantial increase in the number of points to be evaluated and increases the amount of time required to complete the process.
The prior art discloses a number of devices utilizing appropriated methods and apparatus for skeletonization of images used in pattern recognition. For example, U.S. Pat. No. 3,975,709 to Beun et al. and U.S. Pat. No. 5,224,179 to Denker et al. disclose methods of image thinning or skeletonization utilizing at least 3xc3x973 pixel by pixel analysis to thin a character of interest.
Another reference, U.S. Pat. No. 5,335,290 to Cullen et al., teaches a character recognition system by extracting run lengths for each scanline from the bit mapped representation of the document image and classifying the data as image, text or as a horizontal or vertical line. However, there is no teaching of the process of skeletonization by run length comparison which is needed to increase speed of the pattern recognition.
Still another reference, U.S. Pat. No. 4,491,960 to Brown, describes a pattern comparison system wherein a raster scan of a hand print produces a topography to be compared to a given parameters for identification.
Yet another reference, Zhang et al., xe2x80x9cA Fast Parallel Algorithm for Thinning Digital Patternsxe2x80x9d, discloses skeletonization via pixel by pixel comparison and removal of subsequent outer pixels for character thinning.
However, the prior art fails to address the problem of size of data files and speed of skeletonization and does not disclose, teach or even suggest the embodiments of the claimed invention.
To address the requirements described above, the present invention discloses a method, apparatus, and article of manufacture for producing a skeleton from a raster image by overlaying a plurality of tiles on the raster image, wherein each of the tiles identifies a sub-region of the raster image comprised of a plurality of pixels. The sub-regions are selectively skeletonized and then cached for subsequent access. Some or all of the cache is invalidated when one or more of the sub-regions are modified. Only those sub-regions that have been modified are re-skeletonized, on an xe2x80x9cas neededxe2x80x9d basis.